438. 找到字符串中所有字母异位词

题目链接

分析

这个题，跟 76. 最小覆盖子串 非常像，不过却更加的简单，因为 76 题要求最短的子串，而这个题寻找的是字母异位词，也就是说子串的长度是固定的，因此我们不需要像 76 题那样，移动快指针以满足条件，然后移动慢指针来缩短字符串，在这个题中，快指针和慢指针的距离是固定的。
这里重复一下解题思路，首先用一个数组记录目标字符串 p 中每个字符的出现次数，然后定义快指针指向 s 的头部然后，直接比较 s 的 [0,p.toCharArray().length-1] 的子串是否跟 p 是字母异位词，然后新建一个慢指针，指向 s 的第一个字符，然后同时移动快指针和慢指针，每移动一次，更新子串的字符出现次数，同时比较一下 [slow,fast) 这个范围的子串是否与 p 是字母异位词。
比较子串跟 p 是否是字母异位词的方式也很简单，用一个变量 t 表示 p 中的字符在子串中出现的次数，t 的累加方式也很简单

• 移动快指针的时候，如果新加入的字符在子串中出现的次数小于等于字符在 p 中出现的次数，t++
• 移动慢指针的时候，如果移除的字符在子串中出现的次数等于字符在 p 中出现的次数，t--;
  思路跟很简单，和 76. 最小覆盖子串 是差不多的，但是最后写代码的时候还是卡了一下，我们还是要搞清楚 slow 和 fast 指针的含义，严格按照变量定义来写代码。

解题

注意 slow 和 fast 的定义，在第一步从 0 移动 fast 结束的那个 for 循环，我们要清楚此时 fast 指向的是谁，slow 指向的是谁

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<Integer>();
    char[] pChars = p.toCharArray();
    char[] sChars = s.toCharArray();
    if(sChars.length<pChars.length){
        return result;
    }
    int offset = (int)'a';
    int[] charCount = new int[26];
    for(int i=0;i<pChars.length;i++ ){
        int charIndex = (int)pChars[i];
        charCount[charIndex-offset]++;
    }
    int t=0;
    int[] subStrCharCount = new int[26];
    int fast=0;
    // 先移动fast
    for(;fast<pChars.length;fast++){
        int charIndex = (int)sChars[fast];
        if(charCount[charIndex-offset]>0){
            // 是p中的字符才需要计数
            subStrCharCount[charIndex-offset]++;
            if(subStrCharCount[charIndex-offset]<=charCount[charIndex-offset]){
                t++;  
            }
            if(t==pChars.length){
                result.add(0);
            }
        }
    }
    // 此时，fast =p.length
    // 注意，fast指向的是子数组的右边界的下一个元素
    // slow指向的是子数组的左边界
    // 因此 子数组的范围是 [slow,fast)
    int slow =0;
    // 再同时移动fast和slow
    while(fast<sChars.length){
        // 处理 fast 指针
        int fastCharIndex = (int)sChars[fast];
        if(charCount[fastCharIndex-offset]>0){
            // 是p中的字符才需要计数
            subStrCharCount[fastCharIndex-offset]++;
            if(subStrCharCount[fastCharIndex-offset]<=charCount[fastCharIndex-offset]){
                t++;  
            }
        }
        // 处理 slow 指针
        int slowCharIndex = (int)sChars[slow];
        if(charCount[slowCharIndex-offset]>0){
            // 是p中的字符才需要计数
            subStrCharCount[slowCharIndex-offset]--;
            if(subStrCharCount[slowCharIndex-offset]<charCount[slowCharIndex-offset]){
                t--;  
            }
        }
        if(t==pChars.length){
            result.add(slow+1);
        }
        slow++;
        fast++;
    }
    return result;
}

相关题

242. 有效的字母异位词
383. 赎金信
76. 最小覆盖子串